LeetCode-827.最大人工岛-hard

2022-09-18 阅读量 2

似乎😮

写下这篇文章的当天似乎是个愉快的周日，舍友们似乎早早就起来了，我似乎少见地没有被键盘声喊醒，感冒发烧似乎也随着美妙周日的来到悄悄离开，这周似乎做了但又没做很多事。当然，似乎最兴奋的是这周二得到论文被accpet的消息且正好赶上评奖学金。

昨晚，师弟进行学习汇报讲到leetcode，舍友 [甜心] 也打了一场双周赛（赛后讨论了一波，可惜…甜心的代码少写了一行没过掉第三题）。转念一想嘿，似乎感觉好久没刷题了？不如就以每日一题为小甜点，开启这美妙(shit)的周日。

打开chrome 浏览器，输入leetcode.cn，回车！找到每日一题..卧槽？hard 题？再见……

害，还是看一下题目吧。什么？岛屿面积？似乎跟2021/11/18刷的695. 岛屿的最大面积很像啊，是不是用dfs\bfs\并查集？噢！貌似增加了一个新的条件，可以将非岛屿变成岛屿是吧，所以只用把变成岛屿后导致的一系列连锁反应考虑清楚就好了。得，思路清楚了，不如用最酷炫的并查集秀一波（其实是并查集好写…DFS要想好烦，BFS肯定又长又臭）

题目

给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

1
2
3

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

1
2
3

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

1
2
3

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

提示：

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1

题解

先使用并查集（并查集不会？点我）构建出整个岛屿布局（相邻的1组成的块称之为一个岛屿），在着过程中计算出每个岛屿的面积
再找到 0 的点，尝试合并其上下左右岛屿块，并计算面积。
- 注意，上下左右本身有可能就是连接在一起的，所以，注意去重。

class Solution {
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int largestIsland(int[][] grid) {

        int n = grid.length;
        
        // 构建岛屿布局（并查集）
        UnionFind unionFind = new UnionFind(n * n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                // 若当前位置是小岛屿，那尝试跟[右] 和 [下]的元素合并成更大的岛屿
                if(grid[i][j] == 1){
                    if(j+1 < n && grid[i][j+1] == 1){
                        unionFind.union(i*n+j, i*n+j+1);
                    }
                    if(i+1 < n && grid[i+1][j] == 1){
                        unionFind.union(i*n+j, (i+1)*n+j);
                    }
                }
            }
        }

        // Magic! 若当前位置非岛屿，则变成岛屿并跟四周尝试合并成更大的岛屿（这里不是要真合并）
        int ans = -1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] == 0){
                    int curSum = 1;
                    Set<Integer> mergedIsland = new HashSet<>();
                    for(int[] direction: directions){
                        int ni = i + direction[0];
                        int nj = j + direction[1];
                        int curLoc = ni*n + nj;
						
                        // 查看四周位置是否合理、是否是岛屿、是否已经计算过合并面积了
                        if(ni>=0 && ni<n && nj>=0 && nj<n && grid[ni][nj] == 1 
                          && !mergedIsland.contains(unionFind.find(curLoc))){
                            curSum += unionFind.getSize(curLoc);
                            mergedIsland.add(unionFind.find(curLoc));
                        }
                    }
                    ans = Math.max(ans, curSum);
                }
            }
        }
        // 若ans为-1则表示没有为0的元素，那么答案为矩阵的面积n*n
        return ans == -1 ? n * n : ans;
    }

    /* 并查集模板 */
    class UnionFind{
        private int[] parents;
        private int[] size;

        // 构造函数初始化
        UnionFind(int n){
            parents = new int[n];
            size = new int[n];
            for(int i=0;i<n;i++){
                parents[i] = i;
                size[i] = 1;
            }
        }

        // 路径压缩寻找当前元素所在集合的根节点
        public int find(int a){
            if(a != parents[a]){
                parents[a] = find(parents[a]);
            }
            return parents[a];
        }

        // 合并两个集合
        public void union(int a, int b){
            int roota = find(a);
            int rootb = find(b);
            if(roota != rootb){
                parents[roota] = rootb;
                size[rootb] += size[roota];
            }
        }

        // 获取当前元素所在集合的数量
        public int getSize(int a){
            return size[find(a)];
        }
    }
}

并查集相关题目

Leetcode
- 765.情侣牵手-hard
- 200.岛屿数量-medium
- 778.水位上升的泳池中游泳-hard
- 839.相似字符串组-hard
Acwing
- 图中的环
- 修改数组